home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
CD ROM Paradise Collection 4
/
CD ROM Paradise Collection 4 1995 Nov.iso
/
graphics
/
font3d10.zip
/
geometry.cpp
< prev
next >
Wrap
C/C++ Source or Header
|
1994-09-15
|
19KB
|
560 lines
//=================================================================================================
// Geometry.CPP
//-------------------------------------------------------------------------------------------------
//
// Copyright (c) 1994 by Todd A. Prater
// All rights reserved.
//
//=================================================================================================
#include <math.h>
#include <stddef.h>
#include <stdio.h>
#include <iostream.h>
#include "Geometry.H"
#include "List.H"
#include "Config.H"
#define BIG 1.0e30
#define ERR_OUTOFMEMORY 2
#define ERR_NOPOLYFOUND 1
#define NOERROR 0
//===========================================================================================================
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
ostream& operator << (ostream& s, const TRIANGLE& t)
{
s<<"triangle {"<<t.v1<<","<<t.v2<<","<<t.v3<<"}";
return s;
}
//===========================================================================================================
// TRIANGLE::Output (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
void TRIANGLE::Output(ostream& s, ULONG format)
{
switch(format)
{
case RAW:
s<<v1.x<<" "<<v1.y<<" "<<v1.z<<" "
<<v2.x<<" "<<v2.y<<" "<<v2.z<<" "
<<v3.x<<" "<<v3.y<<" "<<v3.z;
break;
case POV_FLAT :
s<<"triangle {"<<v1<<","<<v2<<","<<v3<<"}";
break;
case POV_SMOOTH:
s<<"smooth_triangle {"<<v1<<","<<n1<<","
<<v2<<","<<n2<<","
<<v3<<","<<n3<<"}";
break;
}
}
//===========================================================================================================
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
ostream& operator << (ostream& s, const POLYGON& p)
{
if (p.numpoints==0)
s<<"EMPTY POLYGON\n";
else
{
s<<"POLYGON with "<<p.numpoints<<" sides:\n";
for (int i=0;i<p.numpoints;i++)
s<<" "<<p.pointlist[i]<<"\n";
}
return s;
}
//===========================================================================================================
// POLYGON (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
// These are the constructors for the POLYGON class. The first creates a POLYGON with no vertices, the
// second creates a POLYGON given an array of n points, and the third is a copy constructor.
//===========================================================================================================
POLYGON::POLYGON(void)
{
numpoints = 0;
pointlist = NULL;
orientation = CLOCKWISE;
}
POLYGON::POLYGON(INT n, VECTOR* p)
{
numpoints = n;
pointlist = p;
orientation = findOrientation();
}
POLYGON::POLYGON(POLYGON& P)
{
numpoints = P.numpoints;
pointlist = new VECTOR[numpoints];
for (int i=0;i<numpoints;i++)
pointlist[i]=P.pointlist[i];
orientation = P.orientation;
}
//===========================================================================================================
// POLYGON::findOrientation (PRIVATE)
//-----------------------------------------------------------------------------------------------------------
// This function calculates the orientation of a POLYGON.
//===========================================================================================================
ORIENTATIONTYPE POLYGON::findOrientation(void)
{
DOUBLE area;
INT i;
area = pointlist[numpoints-1].x * pointlist[0].y
- pointlist[0].x * pointlist[numpoints-1].y;
for (i=0;i<numpoints-1;i++)
area += pointlist[i].x * pointlist[i+1].y
- pointlist[i+1].x * pointlist[i].y;
if (area >= 0.0)
return COUNTER_CLOCKWISE;
else
return CLOCKWISE;
}
//===========================================================================================================
// POLYGON::findDeterminant (PRIVATE)
//-----------------------------------------------------------------------------------------------------------
// Finds the orientation of the triangle formed by connecting the POLYGON's p1, p2, and p3 vertices.
//===========================================================================================================
ORIENTATIONTYPE POLYGON::findDeterminant(INT p1, INT p2, INT p3)
{
DOUBLE determinant;
determinant = (pointlist[p2].x-pointlist[p1].x)
*(pointlist[p3].y-pointlist[p1].y)
-(pointlist[p3].x-pointlist[p1].x)
*(pointlist[p2].y-pointlist[p1].y);
if (determinant >= 0.0)
return COUNTER_CLOCKWISE;
else
return CLOCKWISE;
}
//===========================================================================================================
// POLYGON::noneInside (PRIVATE)
//-----------------------------------------------------------------------------------------------------------
// Returns 'FALSE' if any of the POLYGON's vertices in 'vlist' are inside the triangle formed by connecting
// the vertices p1, p2, and p3. 'n' is the number of vertices in 'vlist'. Returns 'TRUE' if no vertices
// are inside that triangle.
//===========================================================================================================
BOOLEAN POLYGON::noneInside(INT p1, INT p2, INT p3, INT n, INT* vlist)
{
INT i,p;
for(i=0;i<n;i++)
{
p=vlist[i];
if((p==p1)||(p==p2)||(p==p3)) continue;
if ( (findDeterminant(p2,p1,p)==orientation)
|| (findDeterminant(p1,p3,p)==orientation)
|| (findDeterminant(p3,p2,p)==orientation)) continue;
else
{
if ( (pointlist[p].x==pointlist[p1].x && pointlist[p].y==pointlist[p1].y)
||(pointlist[p].x==pointlist[p2].x && pointlist[p].y==pointlist[p2].y)
||(pointlist[p].x==pointlist[p3].x && pointlist[p].y==pointlist[p3].y))
continue;
else
return FALSE;
}
}
return TRUE;
}
//===========================================================================================================
// POLYGON::Triangulate (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
// Slices the POLYGON up into a list of triangles. The POLYGON must be non-intersecting. This is done by
// checking each vertex to see whether or not it can be 'chopped off'. If so, that vertex is removed, and
// the process is repeated until there are only three vertices left (only one triangle left).
// Returns the following values upon completion:
//
// ERR_NOPOLYFOUND .......... If there were more than three vertices left, but none of them could
// be 'chopped off'. This usually happens if the polygon intersects
// itself.
//
// NOERROR .................. If the polygon was successfully triangulated.
//
//===========================================================================================================
INT POLYGON::Triangulate(LIST<TRIANGLE>& trilist)
{
TRIANGLE* current_triangle;
INT triangle_count;
INT previous;
INT current;
INT next;
INT* rvl;
INT vertex_count;
DOUBLE current_distance;
ORIENTATIONTYPE current_determinant;
BOOLEAN current_position;
INT i;
VECTOR p1,p2,p3;
BOOLEAN done;
VECTOR n1(0,0,1);
VECTOR n2(0,0,1);
VECTOR n3(0,0,1);
rvl = new INT[numpoints];
for (i=0;i<numpoints;i++)
rvl[i]=i;
vertex_count=numpoints;
while (vertex_count>3)
{
done=FALSE;
previous=vertex_count-1;
current=0;
next=1;
while (current<vertex_count && !done)
{
previous = current-1;
next = current+1;
if (current==0)
previous=vertex_count-1;
else if (current==vertex_count-1)
next=0;
current_determinant = findDeterminant(rvl[previous],
rvl[current],
rvl[next]);
current_position = noneInside(rvl[previous] ,
rvl[current] ,
rvl[next] ,
vertex_count ,
rvl );
if ( (current_determinant==orientation)
&& (current_position==TRUE))
{
done=TRUE;
}
else
{
current++;
}
}
if (!done)
{
cout<<"ERROR: No Polygon Found."<<endl;
return ERR_NOPOLYFOUND;
}
p1=VECTOR(pointlist[rvl[previous]]);
p2=VECTOR(pointlist[rvl[current]]);
p3=VECTOR(pointlist[rvl[next]]);
current_triangle = new TRIANGLE(p1,p2,p3,n1,n2,n3);
trilist.Add(current_triangle);
vertex_count-=1;
for (i=current;i<vertex_count;i++) rvl[i]=rvl[i+1];
}
p1=VECTOR(pointlist[rvl[0]]);
p2=VECTOR(pointlist[rvl[1]]);
p3=VECTOR(pointlist[rvl[2]]);
current_triangle = new TRIANGLE(p1,p2,p3);
trilist.Add(current_triangle);
delete rvl;
return NOERROR;
}
//===========================================================================================================
// POLYGON::Combine (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
void POLYGON::Combine(POLYGON& p)
{
INT i,ni,j;
DOUBLE min_dist;
INT min_i=0;
INT min_j=0;
VECTOR* newpl;
newpl = new VECTOR[numpoints+p.numpoints+2];
min_dist = BIG;
for (i=0;i<numpoints;i++)
for (j=0;j<p.numpoints;j++)
if (dist(pointlist[i],p.pointlist[j])<min_dist)
{
min_dist = dist(pointlist[i],p.pointlist[j]);
min_i = i;
min_j = j;
}
ni=0;
for(i=0 ; i<=min_i ;i++) { newpl[ni]=pointlist[i]; ni++; }
for(i=min_j ; i<p.numpoints ;i++) { newpl[ni]=p.pointlist[i]; ni++; }
for(i=0 ; i<=min_j ;i++) { newpl[ni]=p.pointlist[i]; ni++; }
for(i=min_i ; i<numpoints ;i++) { newpl[ni]=pointlist[i]; ni++; }
numpoints = ni;
delete pointlist;
pointlist = newpl;
}
//===========================================================================================================
// POLYGON::isInside (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
int POLYGON::isInside(POLYGON& p)
{
INT i;
DOUBLE max_inside_x = -BIG; DOUBLE max_outside_x = -BIG;
DOUBLE max_inside_y = -BIG; DOUBLE max_outside_y = -BIG;
DOUBLE min_inside_x = BIG; DOUBLE min_outside_x = BIG;
DOUBLE min_inside_y = BIG; DOUBLE min_outside_y = BIG;
for (i=0;i<p.numpoints;i++)
{
if (p.pointlist[i].x > max_outside_x) max_outside_x = p.pointlist[i].x;
if (p.pointlist[i].y > max_outside_y) max_outside_y = p.pointlist[i].y;
if (p.pointlist[i].x < min_outside_x) min_outside_x = p.pointlist[i].x;
if (p.pointlist[i].y < min_outside_y) min_outside_y = p.pointlist[i].y;
}
for (i=0;i<numpoints;i++)
{
if (pointlist[i].x > max_inside_x) max_inside_x = pointlist[i].x;
if (pointlist[i].y > max_inside_y) max_inside_y = pointlist[i].y;
if (pointlist[i].x < min_inside_x) min_inside_x = pointlist[i].x;
if (pointlist[i].y < min_inside_y) min_inside_y = pointlist[i].y;
}
if ( (max_outside_x < max_inside_x) || (max_outside_y < max_inside_y)
|| (min_outside_x > min_inside_x) || (min_outside_y > min_inside_y) )
return 0;
else
return 1;
}
//===========================================================================================================
// POLYGON::Encloses (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
int POLYGON::Encloses(POLYGON& p)
{
INT i;
DOUBLE max_inside_x = -BIG; DOUBLE max_outside_x = -BIG;
DOUBLE max_inside_y = -BIG; DOUBLE max_outside_y = -BIG;
DOUBLE min_inside_x = BIG; DOUBLE min_outside_x = BIG;
DOUBLE min_inside_y = BIG; DOUBLE min_outside_y = BIG;
for (i=0;i<p.numpoints;i++)
{
if (pointlist[i].x > max_outside_x) max_outside_x = pointlist[i].x;
if (pointlist[i].y > max_outside_y) max_outside_y = pointlist[i].y;
if (pointlist[i].x < min_outside_x) min_outside_x = pointlist[i].x;
if (pointlist[i].y < min_outside_y) min_outside_y = pointlist[i].y;
}
for (i=0;i<numpoints;i++)
{
if (p.pointlist[i].x > max_inside_x) max_inside_x = p.pointlist[i].x;
if (p.pointlist[i].y > max_inside_y) max_inside_y = p.pointlist[i].y;
if (p.pointlist[i].x < min_inside_x) min_inside_x = p.pointlist[i].x;
if (p.pointlist[i].y < min_inside_y) min_inside_y = p.pointlist[i].y;
}
if ( (max_outside_x < max_inside_x) || (max_outside_y < max_inside_y)
|| (min_outside_x > min_inside_x) || (min_outside_y > min_inside_y) )
return 0;
else
return 1;
}
//===========================================================================================================
// POLYGON::Shrink (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
void POLYGON::Shrink(POLYGON& newPoly, DOUBLE shrinkFactor)
{
INT i;
VECTOR current,previous,next;
VECTOR toPrevious,toNext,inPrevious,inNext;
VECTOR inward;
DOUBLE angle;
VECTOR zDir(0,0,1);
if (newPoly.numpoints>0)
{
delete newPoly.pointlist;
newPoly.numpoints = 0;
}
newPoly.pointlist = new VECTOR[numpoints];
newPoly.numpoints = numpoints;
previous = pointlist[numpoints-1];
current = pointlist[0];
next = pointlist[1];
toPrevious = ~(previous-current);
toNext = ~(next-current);
inPrevious = zDir^toPrevious;
inNext = toNext^zDir;
angle = acos(inPrevious%inNext);
inward = ~(inPrevious+inNext)*shrinkFactor;
newPoly.pointlist[0]=current+inward;
previous = pointlist[numpoints-2];
current = pointlist[numpoints-1];
next = pointlist[0];
toPrevious = ~(previous-current);
toNext = ~(next-current);
inPrevious = zDir^toPrevious;
inNext = toNext^zDir;
angle = acos(inPrevious%inNext);
inward = ~(inPrevious+inNext)*shrinkFactor;
newPoly.pointlist[numpoints-1]=current+inward;
for (i=1;i<numpoints-1;i++)
{
previous = pointlist[i-1];
current = pointlist[i];
next = pointlist[i+1];
toPrevious = ~(previous-current);
toNext = ~(next-current);
inPrevious = zDir^toPrevious;
inNext = toNext^zDir;
angle = acos(inPrevious%inNext);
inward = ~(inPrevious+inNext)*shrinkFactor;
newPoly.pointlist[i]=current+inward;
}
}
//===========================================================================================================
// POLYGON::SetDepth (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
void POLYGON::SetDepth(DOUBLE depth)
{
for (INT i=0;i<numpoints;i++)
pointlist[i].z = depth;
}
//===========================================================================================================
// ApproximateQuadraticSpline (PUBLIC)
//-----------------------------------------------------------------------------------------------------------
//===========================================================================================================
VECTOR ApproximateQuadraticSpline(VECTOR cp1, VECTOR cp2, VECTOR cp3, DOUBLE t)
{
DOUBLE i1 = (1-t)*(1-t);
DOUBLE i2 = 2*t*(1-t);
DOUBLE i3 = t*t;
DOUBLE tx = i1*cp1.x + i2*cp2.x + i3*cp3.x;
DOUBLE ty = i1*cp1.y + i2*cp2.y + i3*cp3.y;
DOUBLE tz = cp1.z;
return VECTOR(tx,ty,tz);
}